// Copyright (C) 2011 - Tencent Inc.
// Author: Liu Shaohui (struggleliu@tencent.com)
//
// Created: 09/12/2011 18:10:25
// Description: Dancing link solved the exact cover problem
//

#include <list>
#include <map>

class DancingLinks {
public:
    DancingLinks(int row_num, int col_num, bool ** matrix)
        : m_row_num(row_num), m_col_num(col_num), m_matrix(matrix){
    }

    // 预先选取第row_id
    void PreChooseCol(int row_id);

    bool Search();

    std::list<int>& GetChoosedCols() {
        return m_choose_cols;
    }

private:
    struct DLNode{
        DLNode* left;
        DLNode* right;
        DLNode* up;
        DLNode* down;
        DLNode* header;
        int row_id;
    };
    void InitMatrix();

    void InitNode(int row, int col);

    bool DFSSearch(int depth);

    void CoverCol(DLNode* node);

    void UnCoverCol(DLNode* node);

    void CoverH(DLNode* node);

    void UnCoverH(DLNode* node);

    void CoverV(DLNode* node);

    void UnCoverV(DLNode* node);

    int RightCol(int row) {
        return (row + 1) % m_row_num;
    }

    int LeftCol(int row) {
        return (row - 1 + m_row_num) % m_row_num;
    }

    //  There can be some stratagy to make the search faster
    DLNode* ChooseCol();

private:
    int m_row_num;
    int m_col_num;
    bool ** m_matrix;
    std::map<int, DLNode* > m_node_map;
    DLNode * m_header;
    DLNode* m_root;
    std::list<int> m_choose_cols;
};
